package org.apache.lucene.util.fst;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.io.IOException;

// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {

    private int[] table;
    private int count;
    private int mask;
    private final FST<T> fst;
    private final FST.Arc<T> scratchArc = new FST.Arc<T>();

    public NodeHash(FST<T> fst) {
        table = new int[16];
        mask = 15;
        this.fst = fst;
    }

    private boolean nodesEqual(Builder.UnCompiledNode<T> node, int address) throws IOException {
        final FST<T>.BytesReader in = fst.getBytesReader(0);
        fst.readFirstRealArc(address, scratchArc);
        if (scratchArc.bytesPerArc != 0 && node.numArcs != scratchArc.numArcs) {
            return false;
        }
        for (int arcUpto = 0; arcUpto < node.numArcs; arcUpto++) {
            final Builder.Arc<T> arc = node.arcs[arcUpto];
            if (arc.label != scratchArc.label || !arc.output.equals(scratchArc.output) || ((Builder.CompiledNode) arc.target).address != scratchArc.target || !arc.nextFinalOutput.equals(scratchArc.nextFinalOutput) || arc.isFinal != scratchArc.isFinal()) {
                return false;
            }

            if (scratchArc.isLast()) {
                if (arcUpto == node.numArcs - 1) {
                    return true;
                } else {
                    return false;
                }
            }
            fst.readNextRealArc(scratchArc, in);
        }

        return false;
    }

    // hash code for an unfrozen node.  This must be identical
    // to the un-frozen case (below)!!
    private int hash(Builder.UnCompiledNode<T> node) {
        final int PRIME = 31;
        //System.out.println("hash unfrozen");
        int h = 0;
        // TODO: maybe if number of arcs is high we can safely subsample?
        for (int arcIdx = 0; arcIdx < node.numArcs; arcIdx++) {
            final Builder.Arc<T> arc = node.arcs[arcIdx];
            //System.out.println("  label=" + arc.label + " target=" + ((Builder.CompiledNode) arc.target).address + " h=" + h + " output=" + fst.outputs.outputToString(arc.output) + " isFinal?=" + arc.isFinal);
            h = PRIME * h + arc.label;
            h = PRIME * h + ((Builder.CompiledNode) arc.target).address;
            h = PRIME * h + arc.output.hashCode();
            h = PRIME * h + arc.nextFinalOutput.hashCode();
            if (arc.isFinal) {
                h += 17;
            }
        }
        //System.out.println("  ret " + (h&Integer.MAX_VALUE));
        return h & Integer.MAX_VALUE;
    }

    // hash code for a frozen node
    private int hash(int node) throws IOException {
        final int PRIME = 31;
        final FST<T>.BytesReader in = fst.getBytesReader(0);
        //System.out.println("hash frozen");
        int h = 0;
        fst.readFirstRealArc(node, scratchArc);
        while (true) {
            //System.out.println("  label=" + scratchArc.label + " target=" + scratchArc.target + " h=" + h + " output=" + fst.outputs.outputToString(scratchArc.output) + " next?=" + scratchArc.flag(4) + " final?=" + scratchArc.isFinal());
            h = PRIME * h + scratchArc.label;
            h = PRIME * h + scratchArc.target;
            h = PRIME * h + scratchArc.output.hashCode();
            h = PRIME * h + scratchArc.nextFinalOutput.hashCode();
            if (scratchArc.isFinal()) {
                h += 17;
            }
            if (scratchArc.isLast()) {
                break;
            }
            fst.readNextRealArc(scratchArc, in);
        }
        //System.out.println("  ret " + (h&Integer.MAX_VALUE));
        return h & Integer.MAX_VALUE;
    }

    public int add(Builder.UnCompiledNode<T> node) throws IOException {
        // System.out.println("hash: add count=" + count + " vs " + table.length);
        final int h = hash(node);
        int pos = h & mask;
        int c = 0;
        while (true) {
            final int v = table[pos];
            if (v == 0) {
                // freeze & add
                final int address = fst.addNode(node);
                //System.out.println("  now freeze addr=" + address);
                assert hash(address) == h : "frozenHash=" + hash(address) + " vs h=" + h;
                count++;
                table[pos] = address;
                if (table.length < 2 * count) {
                    rehash();
                }
                return address;
            } else if (nodesEqual(node, v)) {
                // same node is already here
                return v;
            }

            // quadratic probe
            pos = (pos + (++c)) & mask;
        }
    }

    // called only by rehash
    private void addNew(int address) throws IOException {
        int pos = hash(address) & mask;
        int c = 0;
        while (true) {
            if (table[pos] == 0) {
                table[pos] = address;
                break;
            }

            // quadratic probe
            pos = (pos + (++c)) & mask;
        }
    }

    private void rehash() throws IOException {
        final int[] oldTable = table;
        table = new int[2 * table.length];
        mask = table.length - 1;
        for (int idx = 0; idx < oldTable.length; idx++) {
            final int address = oldTable[idx];
            if (address != 0) {
                addNew(address);
            }
        }
    }

    public int count() {
        return count;
    }
}
